'''
https://leetcode.cn/problems/russian-doll-envelopes/description/
'''
import bisect
from functools import cmp_to_key
from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        def compare(a, b):
            if a[0] == b[0]:
                return a[1] > b[1]
            return a[0] < b[0]
        # envelopes.sort(key=cmp_to_key(compare))
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        print(envelopes)

        nums = [env[1] for env in envelopes]
        n = len(nums)
        ends = [nums[0]]
        # nums[i]有效递增位置
        # 当一个nums[i]在ends中查找：
        #       在ends中找 >= nums[i]的最左位置
        #       1) ends[find] == nums[i]    pass
        #       2) ends[find] <  nums[i]    说明当前元素比ends中所有元素都大，新增到ends中
        #       1) ends[find] > nums[i]     说明后续的元素，如果想要找到find+1个长度的递增子序列，那么我就是这时候最好的结尾（足够小）
        for i in range(1, n):
            k = bisect.bisect_left(ends, nums[i])
            if k == len(ends):
                ends.append(nums[i])
            else:
                ends[k] = nums[i]
        return len(ends)